import java.io.*;


public class NumericalCoding {
	public static String code(byte[] x) throws UnsupportedEncodingException {
		int[] tau = Utils.tau(x);
		int[] tauBackup = tau.clone();
		
		Fraction F = new Fraction(0, 1);
		Fraction G = new Fraction(1, 1);
		
		Fraction[] p = new Fraction[Utils.size];
		Fraction[] q = new Fraction[Utils.size + 1];
		q[0] = new Fraction(0, 1);
		
		System.out.println("\\begin{tabular}{|l|l|l|l|l|l|}\\hline");
		System.out.println("$i$ & $x_i$ & $p(x_i)$ & $q(x_i)$ & $F$ & $G$ \\\\\\hline");
		
		for (int i = 0; i < x.length; i++) {
			int n = x.length - i;
			
			char current = new String(new byte[] {x[i]}, "cp1251").charAt(0);
			System.out.print(i + " & " + current + " & ");
			
			for (int j = 1; j <= Utils.size; j++) {
				p[j - 1] = new Fraction(tau[j - 1], n);
				q[j] = q[j - 1].add(p[j - 1]);
			}
			
			int xi = x[i] & 255;
			
			System.out.print(p[xi] + " & " + q[xi] + " & ");
			
			F = F.add(q[xi].multiply(G));
			G = G.multiply(p[xi]);
			
			System.out.print(F + " & ");
			System.out.println(G + "\\\\\\hline");

			tau[xi]--;				
		}
		
		System.out.println("\\end{tabular}");
		
		int z = G.inverse().log2up();
		String out = F.nBitsAfterComma(z).toString(2);
		while (out.length() < z) {
			out = "0" + out;
		}
		return Utils.tauIndex(tauBackup) + "|" + out;
	}
	
	public static void main (String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt"), "cp1251"));
		String input = in.readLine();
		in.close();
		String output = code(input.getBytes("cp1251"));
		System.out.println();
		System.out.println(output);
		System.out.println("Input length: " + input.length() * 8 + " bits");
		System.out.println("Output length: " + (output.length() - 1) + " bits");
		System.out.println("Output-tau: " + (output.indexOf('|')) + " bits");
		System.out.println("Output-data: " + (output.length() - 1 - output.indexOf('|')) + " bits");
	}
}	
